package algorithm.sort;

/**
 * 改进插入排序
 * 通过一个间隔去找一个数据。
 * 最好可以达到 O(n^1.3) 时间复杂度
 *
 * 不稳定
 */
public class ShellSort {
    public static void main(String[] args) {
        System.out.println("希尔排序");

        // 初始化数组队列
        int [] ay = {-1,2,-99,21,0,11,88,-2,66};

        // 分割的标识位置
        int split = 1;
        // 数组长度
        int len = ay.length;
        // 每次递增的倍数
        int avg = 3;

        // knuth 序列
        while (split < len / avg) split = split*avg + 1;

        while (split >= 1){

            for(int i = split; i < len; i++) {
                for (int j = i; j >= split && ay[j] < ay[j - split]; j-=split) {
                    int tmp = ay[j];
                    ay[j] = ay[j - split];
                    ay[j - split] = tmp;
                }
            }


            split /= avg;
        }




        for (int i:ay){
            System.out.print(i + " ");
        }
    }
}
